#pragma once
#include <bits/stdc++.h>
using namespace std;

enum BackgroundColor{
    BLACK = 0,RED=1,
};
template <class KeyType,class ValueType>
struct RBTreeNode{
    typedef RBTreeNode<KeyType,ValueType>* RBTreeNodePtr;
    
    RBTreeNode(pair<KeyType,ValueType> kv = make_pair(KeyType(),ValueType()),BackgroundColor Inicolor =RED)
    : _kv(kv),left(nullptr),right(nullptr),parent(nullptr),color(Inicolor)
    {
        ;
    }
    pair<KeyType,ValueType> _kv;
    RBTreeNodePtr left;
    RBTreeNodePtr right;
    RBTreeNodePtr parent;
    BackgroundColor color;
};


template <class KeyType,class ValueType>
class RBTree{
    private:
    typedef RBTreeNode<KeyType,ValueType>* RBTreeNodePtr;
    RBTreeNodePtr m_root;
    RBTreeNodePtr m_header;

    private:
    RBTreeNodePtr LeftestNode()
    {
        RBTreeNodePtr cur = m_root;
        while(cur && cur->left)
        {
            cur = cur->left;
        }
        return cur;
    }
    
    RBTreeNodePtr RightestNode()
    {
        RBTreeNodePtr cur = m_root;
        while(cur&&cur->right)
        {
            cur = cur->right;
        }
        return cur;
    }
    RBTreeNodePtr  RightRotate(RBTreeNodePtr root)//传要传输的旋转的父节点其父亲所指向的那个节点
    {
        RBTreeNodePtr left = root->left;
        RBTreeNodePtr Childright = left->right;
        
        root->left = Childright;
        if(Childright)
        {
            Childright->parent = root;
        }
        //节点之间的值就算交换完毕
        
        left->right = root;
        root->parent = left;

        return left;
    }
    void Rotate(RBTreeNodePtr parent,RBTreeNodePtr(RBTree<KeyType, ValueType>::*Rotatefunc)(RBTreeNodePtr))
    {
        RBTreeNodePtr PP = parent->parent;
        if(PP && PP!=m_header)
        {
            RBTreeNodePtr Child = (this->*Rotatefunc)(parent);
            if(PP->left == parent)
            {
                PP->left = Child;
                Child->parent = PP;
            }
            else
            {
                PP->right = Child;
                Child->parent = PP;
            }
        }
        else//说明遇见了根节点
        {
            m_root= (this->*Rotatefunc)(parent);
            m_root->parent = m_header;
            m_header ->parent = m_root;
        }
    }
    RBTreeNodePtr LeftRotate(RBTreeNodePtr root)
    {
        RBTreeNodePtr right = root->right;
        RBTreeNodePtr Childleft = right->left;

        root->right = Childleft;
        if(Childleft)
        {
            Childleft->parent = root;
        }

        right->left = root;
        root->parent = right;

        return right;
    }

    bool adjust(RBTreeNodePtr Cur,RBTreeNodePtr CurPrt)
    {
        //在节点插入中，Cur一来应该不会是根节点，调整到根节点，直接退出
        //应该说，父亲不应该会空，应为根节点会直接插入

        RBTreeNodePtr CurGrp = CurPrt->parent;
        RBTreeNodePtr CurUnc= nullptr;
        
        while(Cur && Cur!=m_root)//直到不会是根节点
        {
            if(CurPrt->color==BLACK)
            {
                //理论上说，color节点new的时候默认是红，这里防止出现意外操作下
                Cur->color = RED;
                return true;
            }
            //每次的舅舅节点
            if(CurGrp->left==CurPrt)
            {
                CurUnc = CurGrp->right;
            }
            else{
                CurUnc = CurGrp->left;
            }
            if(CurUnc&& CurUnc->color==RED)//舅舅节点是红色，向上调整
            {
                CurPrt->color = BLACK;
                CurUnc->color = BLACK;
                Cur->color = RED;
                //处理祖孙的颜色变化

                Cur = CurGrp;
                Cur->color = RED;
                //调整其父亲，祖父节点，因为每次舅舅节点都会算，就不需要额外调整
                CurPrt = Cur->parent;
                CurGrp = CurPrt->parent;
            }
            else//舅舅节点是黑色
            {
                if(CurPrt==CurGrp->left)
                {
                    if(Cur==CurPrt->left)
                    {
                        //左左，对祖父节点进行右单旋
                        CurGrp->color = RED;
                        CurPrt->color = BLACK;
                        Rotate(CurGrp,&RightRotate);
                    }
                    else{
                        //左右,先对父亲左单旋，再对祖父右单旋
                        //
                        Cur->color = BLACK;
                        CurGrp->color = CurPrt->color = RED;
                        Rotate(CurPrt,&LeftRotate);
                        Rotate(CurGrp,&RightRotate);
                    }
                }
                else if(CurPrt==CurGrp->right)
                {
                    if(Cur==CurPrt->right)
                    {
                        //右右
                        CurGrp->color = BackgroundColor::RED;
                        CurPrt->color = BLACK;
                        Rotate(CurGrp,&LeftRotate);
                    }
                    else
                    {
                        //右左
                        Cur->color = BLACK;
                        CurGrp->color = CurPrt->color = RED;
                        Rotate(CurPrt,&RightRotate);
                        Rotate(CurGrp,&LeftRotate);
                    }
                }
                //不用在进行调整，至此结束
                break;
            }
        }
        return false;
    }
    public:
    void InorderPrint()
    {
        InorderPrintR(m_root);
        cout<<"\n";
    }
    void InorderPrintR(RBTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return ;
        }
        InorderPrintR(root->left);
        cout<<root->_kv.first<<" ,";
        InorderPrintR(root->right);
    }
    RBTree()
    : m_root(nullptr)
    {
        //
        m_header = new RBTreeNode(make_pair(KeyType(),ValueType()));
        m_header->left = m_header->right = m_header->parent = nullptr;
        m_header->color = BLACK;
    }
    bool insert(const pair<KeyType,ValueType>& kv)
    {
        if(nullptr==m_root)
        {
            //让header指向父亲指向根节点，左指向最小，右指向最大
            m_root = new RBTreeNode<KeyType,ValueType>(kv,BLACK);
            m_header->left = m_root;
            m_header->right = m_root;

            //根节点父节点是header
            m_header->parent = m_root;
            m_root->parent = m_header;
            return true;
        }
        if(kv.first==36)
        {
            int cc = 100;
        }
            RBTreeNodePtr cur = m_root;
            RBTreeNodePtr CurPrt = nullptr;
            while(cur)
            {
                if(cur->_kv.first > kv.first)
                {
                    if(nullptr==cur->left)
                    {
                        cur->left = new RBTreeNode(kv);
                        cur->left->parent = cur;
                        adjust(cur->left,cur);
                        break;
                    }
                    else
                    {
                        cur = cur->left;
                        CurPrt = cur;
                    }
                }
                else if(cur->_kv.first < kv.first)
                {
                    if(nullptr==cur->right)
                    {
                        cur->right = new RBTreeNode(kv);
                        cur->right->parent = cur;
                        adjust(cur->right,cur);
                        break;
                    }
                    else
                    {
                        cur = cur->right;
                        CurPrt = cur;
                    }
                }
                else
                {
                    //已经存在，暂时先不做处理，认为插入失败
                    break;
                    return false;
                }
            }
            m_root->color= BLACK;
            m_header->left = LeftestNode();
            m_header->right = RightestNode();
            return true;
    }
    

    int height(RBTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        return 1+(leftheight>rightheight?leftheight:rightheight);
    }
    vector<vector<pair<pair<KeyType,ValueType>,BackgroundColor>>> LevelPrint()
    {
        const char* COLOR[2] = {"BLACK","RED"};
        cout<<"********************************\n\n";
        vector<vector<pair<pair<KeyType,ValueType>,BackgroundColor>>> res;
        list<RBTreeNodePtr> nodelist(1,m_root);
        int NowNodeNum = 1,nextLevelNodeNum = 0;
        vector<pair<pair<KeyType,ValueType>,BackgroundColor>> nowlevel;
        while(nodelist.size())
        {
            RBTreeNodePtr p = nodelist.front();
            nodelist.pop_front();
            nowlevel.push_back(make_pair(p->_kv,p->color));
            if(p->left)
            {
                nodelist.push_back(p->left);
                nextLevelNodeNum++;
            }
            if(p->right)
            {
                nodelist.push_back(p->right);
                nextLevelNodeNum++;
            }

            if(--NowNodeNum==0)
            {
                res.push_back(nowlevel);
                nowlevel.clear();
                NowNodeNum = nextLevelNodeNum;
                nextLevelNodeNum = 0;
            }
        }
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = 0; j < res[i].size(); j++)
            {
                cout << res[i][j].first.first << " " <<COLOR[res[i][j].second]<<"\t";
            }
            cout<<endl;
        }
        cout<<"********************************\n\n";
        return res;
    }

    bool test()
    {
        RBTreeNodePtr Cur = m_root;
        int count = 1;
        while(Cur)
        {
            if(Cur->color==BLACK)
            {
                count++;
            }
            Cur = Cur->left;
        }
        return Judge(m_root,0,count);
    }
    bool Judge(RBTreeNodePtr root,size_t k,size_t count)
    {
        if(root==nullptr)
        {
            return k+1==count;
        }
        if(root->color==BLACK)
        {
            k++;
        }
        return Judge(root->left,k,count)&&Judge(root->right,k,count);
    }
    
};